package controleur;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

import exception.CaseInaccessibleException;
import exception.HypothesesNonRespecteesException;
import exception.ToutesLesUnitesBloqueesException;

import modele.Plateau;
import modele.Ressources;
import modele.Statut;

public class ControleurPlateau {
	// Variable(s) d'instance
	private final Plateau plateau;
	private int duree;
	
	// Constructeur(s)
	public ControleurPlateau() {
		this.plateau = new Plateau();
		this.chargerMap();
		this.chargerUnites();
		FileInputStream fichier;
		try {
			fichier = new FileInputStream(new File("./fichiers/fichiers.txt"));
			BufferedReader reader = new BufferedReader(new InputStreamReader(fichier));
			
			// Duree du sleep definie en fonction de fichiers.txt
			String duree = reader.readLine();
			duree = reader.readLine();
			duree = reader.readLine();
			duree = reader.readLine();
			if(duree != null && duree.matches("\\d+?")) {
				// S'il s'agit bien d'un nombre...
				this.duree=Integer.parseInt(duree);
			} else {
				this.duree = 500;
				System.out.println("test");
			}
			reader.close();
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
			this.duree = 500;
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
			this.duree = 500;
		}
	}
	
	public ControleurPlateau(Plateau p) {
		this.plateau=p;
		this.chargerUnites();
	}
	
	// Methode(s)
	public List<ControleurUnite> getUnitesPresentes() {
		return this.plateau.getUnitesPresentes();
	}
	
	public ControleurGrapheCase getGraphe() {
		return this.plateau.getGraphe();
	}
	
	public ControleurUnite getUnite(int numeroUnite) {
		if(numeroUnite < this.getUnitesPresentes().size()) {
			return this.getUnitesPresentes().get(numeroUnite);
		} else {
			return null;
		}
	}
	
	private void ajouterUnite(int[] informationsUnite) throws CaseInaccessibleException {
		// On ajoute une unité au plateau
		ControleurCoordonnee depart = new ControleurCoordonnee(informationsUnite[1], informationsUnite[2]);
		ControleurCoordonnee arrivee = new ControleurCoordonnee(informationsUnite[3], informationsUnite[4]);
		ControleurObjectif objectif = new ControleurObjectif(depart, arrivee);
		if(this.getGraphe().get(depart).getStatut().equals(Statut.ACCESSIBLE)) {
			if(this.getGraphe().get(depart).getLabel().charAt(0)!='a') {
				ControleurUnite unite = new ControleurUnite(objectif, informationsUnite[0]);
				this.getUnitesPresentes().add(unite);
		
				// On rend la case occupee par l'unite inaccessible
				this.changerStatutCasePlateau(depart.getX(), depart.getY(), Statut.INACCESSIBLE, unite);
			
				try {
					this.definirArriveeUnite(unite, arrivee);
				} catch(CaseInaccessibleException e) {
					unite.getObjectif().setArrivee(depart);
				}
			} else {
				throw new CaseInaccessibleException("ajoutSurCaseArrivee");
			}
		} else {
			throw new CaseInaccessibleException("ajoutUniteSurCaseInaccessible");
		}
	}
	
	private void definirArriveeUnite(ControleurUnite unite, ControleurCoordonnee arrivee) throws CaseInaccessibleException {
		if(unite != null && arrivee != null) {
			if(this.getGraphe().get(arrivee).getStatut().equals(Statut.ACCESSIBLE)) {
				if(this.getGraphe().get(arrivee).getLabel().charAt(0)!='a') {
					// On affecte la case d'arrivee sans la rendre inaccessible
					this.getGraphe().get(arrivee).setLabel("a"+unite.getLabel());
				} else {
					throw new CaseInaccessibleException("arriveeSurCaseArrivee");
				}
			} else {
				throw new CaseInaccessibleException("arriveeSurCaseInaccessible");
			}
		}
	}
	
	public void definirObjectifUnite(ControleurObjectif objectif, ControleurUnite unite) {
		if(objectif!=null && unite != null) {
			try {
				this.definirArriveeUnite(unite, objectif.getArrivee());
				unite.setObjectif(objectif);
			} catch (CaseInaccessibleException e) {
				e.printStackTrace();
			}
		}
	}
	
	public void calculerLesTrajectoires() {
		for(int i = 0; i < this.getUnitesPresentes().size(); i++) {
			if(!this.getUnite(i).estArrivee()) {
				this.definirTrajectoireUnite(this.getUnite(i));
			}
		}
	}
	
	public void definirTrajectoireUnite(ControleurUnite unite) {
		// On calcule la trajectoire de l'unite
		ControleurTrajectoire trajectoire;
		try {
			trajectoire = this.getTrajectoireUnite(unite);
			unite.setTrajectoire(trajectoire);
		} catch (HypothesesNonRespecteesException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	public void chargerMap() {
		try {
			// Declaration
			int character;
			int i = 0; // Lignes
			int j = 0; // Colonnes
			String filePath;
			FileInputStream fichierMap = new FileInputStream(new File("./fichiers/fichiers.txt"));
			BufferedReader reader = new BufferedReader(new InputStreamReader(fichierMap));
			filePath = reader.readLine();
			reader.close();
			if(filePath != null) {
				fichierMap = new FileInputStream(new File(filePath));
				reader = new BufferedReader(new InputStreamReader(fichierMap));
				
				while((character = reader.read()) != -1 && i < Ressources.NOMBRE_DE_LIGNES) {
					character = Character.getNumericValue(character);
					if(character == 1) { // la case est inaccessible
						this.changerStatutCasePlateau(i, j, Statut.INACCESSIBLE, null);
					}
					if(character == 0 || character == 1) {
						j++;
					}
					if(j == Ressources.NOMBRE_DE_COLONNES) {
						j=0;
						i++;
					}
				}
				reader.close();
			}
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	public void chargerUnites() {
		// On charge le fichier qui contient les unites qui seront sur le plateau
		// ainsi que leur point de depart et d'arrivee
		try {
			// Declaration
			int character;
			int indiceInformations = 0;
			int[] informationsUnite = new int[5];
			String filePath;
			
			FileInputStream fichierUnites = new FileInputStream(new File("./fichiers/fichiers.txt"));
			BufferedReader reader = new BufferedReader(new InputStreamReader(fichierUnites));
			filePath = reader.readLine();
			filePath = reader.readLine();
			reader.close();
			
			if(filePath!=null) {
				fichierUnites = new FileInputStream(new File(filePath));
				reader = new BufferedReader(new InputStreamReader(fichierUnites));
				
				while((character = reader.read()) != -1) {
					// On verifie s'il s'agit d'un nombre et si celui-ci ne depasse pas les limites du plateau
					character = Character.getNumericValue(character);
					if(character >= 0 && (character < Ressources.NOMBRE_DE_COLONNES || character < Ressources.NOMBRE_DE_LIGNES)) {
						informationsUnite[indiceInformations] = character;
						indiceInformations++;
						if(indiceInformations==5) {
							try {
								this.ajouterUnite(informationsUnite);
							} catch (CaseInaccessibleException e) {
								e.printStackTrace();
							}
							indiceInformations=0;
						}
					}
				}
				reader.close();
			}
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	public ControleurTrajectoire getTrajectoireUnite(ControleurUnite unite) throws HypothesesNonRespecteesException {
		return this.getGraphe().calculPlusCourtChemin(unite.getObjectif());
	}
	
	public void changerStatutCasePlateau(int lig, int col, Statut statut, ControleurUnite unite) {
		this.getGraphe().changerStatutCasePlateau(lig, col, statut, unite);
	}
	
	@Override
	public String toString() {
		//return this.getGraphe().toString();
		String retour = "";
		for(int i = 0; i < this.getGraphe().taille(); i++) {
			retour += this.getGraphe().get(i, i).getLabel()+"\t";
			if(((i+1)%Ressources.NOMBRE_DE_COLONNES)==0 && i!=0) {
				retour += "\n";
			}
		}
		return retour;
	}
	
	public void deplacerLesUnites() {
		for(int i = 0; i < this.getUnitesPresentes().size(); i ++) {
			if(this.getUnite(i).getTrajectoire().taille()!=0) {
				this.deplacerEntierement(this.getUnite(i));
			}
		}
	}
	
	public void deplacer(ControleurUnite unite) {
		this.changerStatutCasePlateau(unite.getCoordonneeActuelle().getX(), unite.getCoordonneeActuelle().getY(), Statut.ACCESSIBLE, null);
		ControleurCoordonnee mouvement = unite.deplacer();
		if(mouvement != null) {
			this.changerStatutCasePlateau(mouvement.getX(), mouvement.getY(), Statut.INACCESSIBLE, unite);
		} else {
			this.changerStatutCasePlateau(unite.getCoordonneeActuelle().getX(), unite.getCoordonneeActuelle().getY(), Statut.INACCESSIBLE, unite);
		}
	}
	
	public void deplacerEntierement(ControleurUnite unite) {
		for(int i = 0; i < unite.getTrajectoire().taille()-1; i++) {
			this.deplacer(unite);
			Controleur.getInstance().getVue().afficher(this);
		}
	}
	
	public List<ControleurUnite> unitesNonArrivees() {
		ControleurUnite unite;
		List<ControleurUnite> nonArrivees = new ArrayList<ControleurUnite>();
		for(int i = 0; i < this.getUnitesPresentes().size(); i++) {
			unite=this.getUnite(i);
			if(!unite.estArrivee()) {
				nonArrivees.add(unite);
			}
		}
		return nonArrivees;
	}
	
	public void melangerLesTrajectoires5() throws ToutesLesUnitesBloqueesException {
		// Melange les trajectoires
		// Detection de cycle a chaque mouvement
		// On cherche la meilleure solution en fonction de l'unite choisie en premier
		
		// On calcule les trajectoires
		this.calculerLesTrajectoires();
		
		// On declare la liste des unites non arrivees
		List<ControleurUnite> nonArrivees;
		
		int i = 0;
		boolean peutBouger = false;
		ControleurUnite unite;
		ControleurCoordonnee prochainMouvement;
		ControleurGraphe graphe;
		ControleurGraphe sauvegarde;
		List<ControleurUnite> peuventBouger;
		List<ControleurUnite> peuventBougerFinal;
		
		// Plateau temporaire
		String[][] plateau;
		
		while((nonArrivees = this.unitesNonArrivees()).size()!=0) {
			peuventBougerFinal = new ArrayList<ControleurUnite>();
			for(int j = 0; j < nonArrivees.size(); j++) {
				plateau = this.construirePlateauAlgo4();
				peuventBouger = new ArrayList<ControleurUnite>();
				i = 0;
				peutBouger = false;
				graphe = new ControleurGraphe(this.getUnitesPresentes().size());
				graphe.completer(plateau, this);
				// On récupère l'unité, ses coordonnées, et son prochain mouvement
				unite = nonArrivees.get(j);
				prochainMouvement = unite.getTrajectoire().get(unite.getTrajectoire().getIndiceActuel()+1);
				
				// Verifie si le deplacement est legal
				peutBouger=this.estLegal2(plateau, unite, prochainMouvement, peuventBouger);
				if(peutBouger) {
					// On actualise le graphe en supposant le deplacement possible
					graphe.enleverUnite(unite.getLabel());
					graphe.ajoutUnite(unite, this, plateau);
					// S'il n'y en a pas, on actualise le plateau et on ajoute l'unite
					if(!this.detecterCycle2(graphe)) {
						peuventBouger.add(unite);

						plateau[unite.getCoordonneeActuelle().getX()][unite.getCoordonneeActuelle().getY()]="O";
						plateau[prochainMouvement.getX()][prochainMouvement.getY()]=""+unite.getLabel();
						
						while(i < nonArrivees.size()) {
							if(i != j) {
								// On instancie le graphe et on l'initialise en fonction de l'etat actuel du plateau
								graphe = new ControleurGraphe(this.getUnitesPresentes().size());
								graphe.completer(plateau, this);
								// On récupère l'unité, ses coordonnées, et son prochain mouvement
								unite = nonArrivees.get(i);
								
								prochainMouvement = unite.getTrajectoire().get(unite.getTrajectoire().getIndiceActuel()+1);
								// Verifie si le deplacement est legal
								peutBouger=this.estLegal2(plateau, unite, prochainMouvement, peuventBouger);
								if(peutBouger) {
									// On fait une copie du graphe
									sauvegarde = new ControleurGraphe(graphe);
									// On actualise le graphe en supposant le deplacement possible
									graphe.enleverUnite(unite.getLabel());
									graphe.ajoutUnite(unite, this, plateau);
									// S'il n'y en a pas, on actualise le plateau et on ajoute l'unite
									if(!this.detecterCycle2(graphe)) {
										peuventBouger.add(unite);
										
										plateau[unite.getCoordonneeActuelle().getX()][unite.getCoordonneeActuelle().getY()]="O";
										plateau[prochainMouvement.getX()][prochainMouvement.getY()]=""+unite.getLabel();
									} else {
										graphe = new ControleurGraphe(sauvegarde);
									}
								}
							}
							i++;
						}
					}
				}
				if(peuventBouger.size() > peuventBougerFinal.size()) {
					peuventBougerFinal= new ArrayList<ControleurUnite>(peuventBouger);
				}
			}
			for(int k = 0; k < peuventBougerFinal.size(); k++) {
				this.deplacer(peuventBougerFinal.get(k));
			}
			Controleur.getInstance().afficher();
			try {
				Thread.sleep(this.duree);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
	}
	
	public void melangerLesTrajectoires4() throws ToutesLesUnitesBloqueesException {
		// On detecte les cycles afin de déterminer si un mouvement est possible
		
		// On calcule les trajectoires
		this.calculerLesTrajectoires();
		
		// On declare la liste des unites non arrivees
		List<ControleurUnite> nonArrivees;
		
		int i = 0;
		boolean peutBouger = false;
		ControleurUnite unite;
		ControleurCoordonnee prochainMouvement;
		ControleurGraphe graphe;
		
		// Maintenant on deplace les unites jusqu'a ce qu'elles soient toutes arrivees
		while((nonArrivees = this.unitesNonArrivees()).size()!=0) {
			i = 0;
			peutBouger = false;
			while(i < nonArrivees.size()) {
				// On instancie le graphe et on l'initialise en fonction de l'etat actuel du plateau
				graphe = new ControleurGraphe(this.getUnitesPresentes().size());
				graphe.completer(this);
				// On récupère l'unité, ses coordonnées, et son prochain mouvement
				unite = nonArrivees.get(i);
				
				prochainMouvement = unite.getTrajectoire().get(unite.getTrajectoire().getIndiceActuel()+1);
				
				// Verifie si le deplacement est legal
				peutBouger=this.estLegal(this.getGraphe(), prochainMouvement, unite.getLabel());
				if(peutBouger) {
					// On actualise le graphe en supposant le deplacement possible
					graphe.enleverUnite(unite.getLabel());
					graphe.ajoutUnite(unite, this, this.getGraphe());
					// S'il n'y en a pas, on actualise le plateau et on ajoute l'unite
					if(!this.detecterCycle2(graphe)) {
						this.deplacer(unite);
					}
				}
				i++;
			}
			Controleur.getInstance().afficher();
			try {
				Thread.sleep(this.duree);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
	}
	
	public void melangerLesTrajectoires3() throws ToutesLesUnitesBloqueesException {
		// Melange les trajectoires de toutes les unites presentes sur le plateau
		// Plusieurs unites peuvent bouger au cours d'une meme periode
		// On alterne l'unite choisie en premier afin de choisi la meilleure solution possible
		
		// On calcule les trajectoires
		this.calculerLesTrajectoires();
		
		// On declare la liste des unites non arrivees
		List<ControleurUnite> nonArrivees;
		//on va maintenir l'invariant :
			//toutes les unites de "peuventBouger" peuvent bouger en meme temps
			//lors du prochain instant, sans faire de mouvement illegal, et sans créer de cycle
		List<ControleurUnite> peuventBouger = new ArrayList<ControleurUnite>();
		List<ControleurUnite> peuventBougerFinal;
				
		int i = 0;
		boolean peutBouger = false;
		ControleurUnite unite;
		ControleurCoordonnee prochainMouvement;
				
		// Maintenant on deplace les unités jusqu'à ce qu'elles soient toutes arrivées
		while((nonArrivees = this.unitesNonArrivees()).size()!=0) {
			peuventBougerFinal = new ArrayList<ControleurUnite>();
			// On parcourt toutes les unités
			for(int indiceUnite = 0; indiceUnite < nonArrivees.size(); indiceUnite++) {
				// Pour chaque unité, si elle peut bouger on la selectionne
				i = 0;
				peutBouger=false;
				peuventBouger=new ArrayList<ControleurUnite>();
				unite = nonArrivees.get(indiceUnite);
				if(this.unitePeutBouger(unite)) {
					peuventBouger.add(unite);
					// On regarde ensuite avec cette unite choisie, combien d'autres peuvent bouger
					while(i < nonArrivees.size()) {
						unite = nonArrivees.get(i);
						peutBouger=this.unitePeutBouger(unite);
						if(peutBouger) {
							// Prochain mouvement de l'unité qu'on souhaite ajouter à la liste
							prochainMouvement = unite.getTrajectoire().get(unite.getTrajectoire().getIndiceActuel()+1);
							// On verifie si un deplacement de l'unite risque de géner la fin de trajectoire des autres
							if(this.geneLesUnitesDejaChoisies(prochainMouvement, peuventBouger)) {
								// Si ce n'est pas le cas, on ajoute l'unite à la liste des unités pouvant bouger
								peuventBouger.add(unite);
							}
						}
						i++;
					}
					if(peuventBouger.size() > peuventBougerFinal.size()) {
						// Si il y a plus d'unités qui peuvent bouger en choisissant l'unité indiceUnite en premier, alors la liste 
						// finale des unités pouvant bouger devient la liste actuellement construite
						peuventBougerFinal = new ArrayList<ControleurUnite>(peuventBouger);
					}
				}
			}
			for(int k = 0; k < peuventBouger.size(); k++) {
				this.deplacer(peuventBouger.get(k));
			}
			Controleur.getInstance().afficher();
			try {
				Thread.sleep(this.duree);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			peuventBougerFinal = new ArrayList<ControleurUnite>();
		}
	}
	
	public void melangerLesTrajectoires2() throws ToutesLesUnitesBloqueesException {
		// Melange les trajectoires de toutes les unites presentes sur le plateau
		// Plusieurs unites peuvent bouger au cours d'une meme periode
		
		// On calcule les trajectoires
		this.calculerLesTrajectoires();
		
		// On declare la liste des unites non arrivees
		List<ControleurUnite> nonArrivees;
		// On declare la liste des unite qui peuvent bouger
		List<ControleurUnite> peuventBouger = new ArrayList<ControleurUnite>();
				
		int i = 0;
		boolean peutBouger = false;
		ControleurUnite unite;
		ControleurCoordonnee prochainMouvement;
				
		// Maintenant on deplace les unites jusqu'a ce qu'elles soient toutes arrivees
		while((nonArrivees = this.unitesNonArrivees()).size()!=0) {
			i = 0;
			peutBouger = false;
			peuventBouger=new ArrayList<ControleurUnite>();
			while(i < nonArrivees.size()) {
				unite = nonArrivees.get(i);
				// Peut bouger si aucune unité ne se trouve sur sa fin de trajectoire
				peutBouger=this.unitePeutBouger(unite);
				if(peutBouger) {
					// Prochain mouvement de l'unité qu'on souhaite ajouter à la liste
					prochainMouvement = unite.getTrajectoire().get(unite.getTrajectoire().getIndiceActuel()+1);
					// On verifie si un deplacement de l'unité risque de géner la fin de trajectoire des autres
					if(this.geneLesUnitesDejaChoisies(prochainMouvement, peuventBouger)) {
						peuventBouger.add(unite);
					}
				}
				i++;
			}
			if(peuventBouger.size()==0) { // code mort
				throw new ToutesLesUnitesBloqueesException();
			} else {
				// On fait ensuite bouger les unités
				for(int k = 0; k < peuventBouger.size(); k++) {
					this.deplacer(peuventBouger.get(k));
				}
				Controleur.getInstance().afficher();
				try {
					Thread.sleep(this.duree);
				} catch (InterruptedException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
		}
	}
	
	public void melangerLesTrajectoires1() throws ToutesLesUnitesBloqueesException {
		// Melange les trajectoires de toutes les unites presentes sur le plateau
		// Une seule unite ne peut bouger a la fois
		
		// On calcule les trajectoires
		this.calculerLesTrajectoires();
		
		// On declare la liste des unites non arrivees
		List<ControleurUnite> nonArrivees;
		
		int i = 0;
		boolean peutBouger = false;
		ControleurUnite unite;
		
		// Maintenant on deplace les unites jusqu'a ce qu'elles soient toutes arrivees
		while((nonArrivees = this.unitesNonArrivees()).size()!=0) {
			i = 0;
			peutBouger = false;
			while(i < nonArrivees.size() && !peutBouger) {
				unite = nonArrivees.get(i);
				// Vérifie si une autre unité est présente sur la fin de trajectoire
				peutBouger=this.unitePeutBouger(unite);
				if(!peutBouger) {
					i++;
				} else {
					this.deplacer(unite);
					Controleur.getInstance().afficher();
					try {
						Thread.sleep(this.duree);
					} catch (InterruptedException e) {
						// TODO Auto-generated catch block
						e.printStackTrace();
					}
				}
			}
			if(i == nonArrivees.size()) {
				// Code mort
				throw new ToutesLesUnitesBloqueesException();
			}
		}
	}
	
	public boolean geneLesUnitesDejaChoisies(ControleurCoordonnee prochainMouvement, List<ControleurUnite> peuventBouger) {
		boolean peutBouger = true;
		int indiceTrajectoire;
		int j = 0;
		while(j < peuventBouger.size() && peutBouger) {
			indiceTrajectoire = peuventBouger.get(j).getTrajectoire().getIndiceActuel()+1;
			while(indiceTrajectoire < peuventBouger.get(j).getTrajectoire().taille() && peutBouger) {
				if(prochainMouvement.equals(peuventBouger.get(j).getTrajectoire().get(indiceTrajectoire))) {
					peutBouger=false;
				}
				indiceTrajectoire++;
			}
			j++;
		} 
		return peutBouger;
	}
	
	public boolean unitePeutBouger(ControleurUnite unite) {
		int j = unite.getTrajectoire().getIndiceActuel()+1;
		boolean peutBouger=true;
		ControleurCoordonnee prochainDeplacement;
		while(j < unite.getTrajectoire().taille() && peutBouger) {
			// On regarde si une unite est presente sur la fin du parcours de l'unite
			prochainDeplacement = unite.getTrajectoire().get(j);
			if(this.getGraphe().get(prochainDeplacement).getUnitePresente()!=null) {
				peutBouger=false;
			}
			j++;
		}
		return peutBouger;
	}
	
	public boolean unitePeutBouger2(ControleurUnite unite) {
		int j = unite.getTrajectoire().getIndiceActuel()+1;
		if(j < unite.getTrajectoire().taille()) {
			ControleurCoordonnee prochainDeplacement=unite.getTrajectoire().get(j);
			return this.getGraphe().get(prochainDeplacement).getUnitePresente()==null;
		} else {
			return false;
		}
	}
	
	public ControleurUnite unitePresenteSurCase(ControleurCoordonnee coordonnee) {
		return this.plateau.getGraphe().get(coordonnee).getUnitePresente();
	}
	
	private String[][] construirePlateauAlgo4() {
		String label;
		String[][] plateau = new String[Ressources.NOMBRE_DE_LIGNES][Ressources.NOMBRE_DE_COLONNES];
		for(int i = 0; i < Ressources.NOMBRE_DE_LIGNES; i++) {
			for(int j = 0; j < Ressources.NOMBRE_DE_COLONNES; j++) {
				label = this.plateau.getGraphe().get(new ControleurCoordonnee(i, j)).getLabel();
				plateau[i][j]=new String(label);
			}
		}
		return plateau;
	}
	
	private boolean estLegal(ControleurGrapheCase graphe, ControleurCoordonnee coordonnee, int numeroUnite) {
		if(graphe.get(coordonnee).getLabel().equals("O") || graphe.get(coordonnee).getLabel().equals("a"+numeroUnite)) {
			return true;
		} else {
			return false;
		}
	}
	
	private boolean estLegal2(String[][] plateau, ControleurUnite unite, ControleurCoordonnee coordonnee, List<ControleurUnite> peuventBouger) {
		boolean result = false;
		int i = 0;
		if(plateau[coordonnee.getX()][coordonnee.getY()].matches("\\d")) {
			while(i < peuventBouger.size() && !result) {
				result = (""+peuventBouger.get(i).getLabel()).equals(plateau[coordonnee.getX()][coordonnee.getY()]);
				i++;
			}
		} else {
			result = plateau[coordonnee.getX()][coordonnee.getY()].equals("O") || plateau[coordonnee.getX()][coordonnee.getY()].equals("a"+unite.getLabel());
		}
		return result;
	}
	
	/*
	 * Ne marche pas
	 * Methode abandonnee et refaite en dessus
	 * private boolean detecterCycle(ControleurGraphe graphe) {
		// On declare les listes
		List<Integer> aVisiter = new ArrayList<Integer>();
		List<Integer> marques = new ArrayList<Integer>();
		List<Integer> voisins = new ArrayList<Integer>();
		
		// AUtres variables
		int unite = 0;
		int i = 0;
		int j = 0;
		boolean stop;
		boolean cycle = false;
		
		while(marques.size()!=this.getUnitesPresentes().size() && !cycle) {
			// On cherche une unite
			if(aVisiter.size()==0) {
				stop = false;
				i = 0;
				// on cherche une unite pas encore visitee
				while(i < this.getUnitesPresentes().size() && !stop) {
					if(!marques.contains(i)) {
						unite = i;
						stop=true;
					} else {
						i++;
					}
				}
			} else {
				unite = aVisiter.get(0);
				aVisiter.remove(0);
			}
		
			// On marque cette unite
			marques.add(unite);
			
			// On met ses voisins dans aVisiter
			voisins = graphe.getVoisins(unite);
			ControleurPlateau.fusionnerListes(aVisiter, voisins);
			
			j=0;
			while(j < aVisiter.size() && !cycle) {
				if(marques.contains(aVisiter.get(j))) {
					voisins = graphe.getVoisins(j);
					if(voisins.size() != 0 && !marques.containsAll(voisins)) {
						cycle = true;
					}
				}
				j++;
			}
		}
		return cycle;
	}*/
	
	public boolean detecterCycle2(ControleurGraphe graphe) {
		boolean cycle = false;
		int i = 0;
		int j = 0;
		List<Integer> marques;
		List<Integer> aVisiter;
		List<Integer> voisins;
		while(i < graphe.size() && !cycle) {
			voisins=graphe.getVoisins(i);
			j=0;
			while(j < voisins.size() && !cycle) {
				aVisiter = new ArrayList<Integer>();
				marques = new ArrayList<Integer>();
				cycle = this.detecterCycle3(graphe, i, voisins.get(j), marques, aVisiter);
				j++;
			}
			i++;
		}
		return cycle;
	}
	
	private boolean detecterCycle3(ControleurGraphe graphe, int noeudDepart, int noeudActuel, List<Integer> marques, List<Integer> aVisiter) {
		marques.add(noeudActuel);
		if(noeudActuel == noeudDepart) {
			return true;
		} else {
			ControleurPlateau.fusionnerListes(aVisiter, graphe.getVoisins(noeudActuel));
			for(int i = 0; i < aVisiter.size(); i++) {
				if(marques.contains(aVisiter.get(i))) {
					aVisiter.remove(i);
					i--;
				}
			}
			if(aVisiter.size()==0) {
				return false;
			} else {
				noeudActuel = aVisiter.get(0);
				aVisiter.remove(0);
				return this.detecterCycle3(graphe, noeudDepart, noeudActuel, marques, aVisiter);
			}
		}
	}
	
	// Methode(s) statique(s)
	public static void fusionnerListes(List<Integer> a, List<Integer> b) {
		for(int i = 0; i < b.size(); i++) {
			if(!a.contains(b.get(i))) {
				a.add(b.get(i));
			}
		}
	}
}
